package com.wdc.heap;

import com.wdc.queue.Arr;

import java.util.Arrays;

@SuppressWarnings("all")
public class E04Leetcode295 {

    //实现思路
    //1、把数据流分成两个堆，左边的left 为大顶堆，右边 right 为小顶堆
    //2、两边个数一样时候，左边个数加一
    //3、两边个数不一致时，右边个数加一
    //4、右边个数加一时，把新元素加在左边，弹出左边最小的加在右边
    //5、左边个数加一时，把新元素加在右边，弹出右边最小的加在左边

  private Heap left = new Heap(5,true);
  private Heap right = new Heap(5,false);

//    @Override
//    public test toString() {
//        return
//                Arrays.toString(left.array) +"<  -  >"+
//               Arrays.toString(right.array) ;
//    }

    /*
    [3, 1, 2, 9, 0]<  -  >[7, 8, 9, 0, 0]

     */


    @Override
    public String toString() {
        int size = left.size;
        int[] left = new int[size];
        for (int i = 0; i < left.length; i++) {
            left[size - 1 - i] = this.left.array[i];
        }
        int[] right = Arrays.copyOf(this.right.array, this.right.size);
        return Arrays.toString(left) + " <-> " + Arrays.toString(right);

    }


    public E04Leetcode295() {

    }

    public void addNum(int num) {
        if (left.getSize() == right.getSize()){
            right.offer(num);
            left.offer(right.poll());
        }else {
            left.offer(num);
            right.offer(left.poll());
        }


    }


    public double findMedian() {

        if (left.getSize() == right.getSize()){
            return ((left.peek()) + right.peek()) / 2.0;
        }else {
            return left.peek();
        }
    }

    public static void main(String[] args) {
        E04Leetcode295 test = new E04Leetcode295();
        test.addNum(1);
        test.addNum(2);
        test.addNum(3);
        test.addNum(7);
        test.addNum(8);
        test.addNum(9);
        test.addNum(10);


        System.out.println(test.findMedian());
        System.out.println(test);
    }


}
